import java.util.Arrays;

/**
 * 插入排序法
 * 插入排序通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。
 * 类似于整理扑克牌。
 * 第i轮的时候，前i张牌是有序的。
 *
 * 最优情况：
 * 当输入的数据已经是正序时，只需遍历一次列表：O(N)
 * 最坏情况：
 * 当输入的数据是反序时，每次插入都需要移动所有已排序元素：O(n²)
 *
 * @author Liu Yicong
 * @date 2025/9/21
 */
public class InsertSort {
	public static Integer[] insertSort(Integer[] arr) {
		int n = arr.length;
		// 从左往右依次遍历每一个元素为当前需要插入的元素
		for (int i = 1; i < n; i++) {
			int curr = arr[i];  // 记录需要插入的元素(将第i张牌抽出来)

			// 从已经排序的序列最右边的开始比较，找到比其小的数(找到第i张牌应该插入的位置)
			int j = i;
			while (j > 0 && curr < arr[j - 1]) {
				arr[j] = arr[j - 1]; // 将大于第i张牌的牌向后移动一格
				j--;
			}

			// 存在比其小的数，插入
			if (j != i) {
				arr[j] = curr;
			}
		}
		return arr;
	}

	public static void main(String[] args) {
		Integer[] arr = {1, 5, 3, 2, 8, 6, 4, 7};
		System.out.println(Arrays.toString(insertSort(arr)));
	}
}
